import numpy as np
from util import *
import copy
import pickle
import pymetis
from pymetis import Options 
import scipy.sparse as sp
from itertools import cycle
import random
# import hashlib
# import torch
import json
import os
import math
from Method.GA_for_init_ms_deploy import GA_algorithm
#在算法层面，不知道即将调度的task的dealing time和他的子任务数量


class OurMethod:
    def __init__(self,cloud_system):
        self.remove_idle_persit_time=1000
        
        self.cloud_system=cloud_system
        self.env=cloud_system.env
        self.print_level=cloud_system.print_level
        # self.neural_network=None
        
        # self.ms_migration=cloud_system.args.our_method_migration
        ####################################
        #call info
        self.ms_call_matrix=None
        ####################################
        #id
        self.ms_id_list_exist=None
        #kind
        self.ms_kind_list_exist=None
        #cluster
        self.ms_node_index_exist=None
        #记录微服务类型的数量
        self.ms_kind_to_number=None
        ####################################
        self.network_deploy_result=False
        
        self.buffer_ms_num=2
        #记录结束工作的时间
        self.ms_obj_to_end_time={}
        
        return
        
    def init_deploy(self):
        # self.init_deploy_with_buffer()
        self.init_deploy_with_GA()
        
    def init_deploy_with_GA(self):
        init_deploy_strategy_file_path=self.cloud_system.args.history_trace_file+f"_{self.cloud_system.args.bare_metal_node_num}.GA_init_deploy"
        if os.path.exists(init_deploy_strategy_file_path):
            with open(init_deploy_strategy_file_path, "rb") as file:
                storage_data=pickle.load(file)
                spec_ms_kind_list=storage_data["ms_kind_list"]
                spec_node_index_list=storage_data["node_index_list"]
                self.cloud_system.ms_kind_to_resource_need=storage_data["resource_cost"]
                self.execute_init_deploy(spec_ms_kind_list, spec_node_index_list)
        else:
            if self.cloud_system.print_level>1:
                print("get init deploy strategy...")
            system_ms_kind_list=self.cloud_system.ms_kind_list
            weight_matrix_t = self.get_weight_matrix(system_ms_kind_list)
            cpu_cost_t = []
            mem_cost_t = []
            disk_cost_t = []
            for ms_kind in system_ms_kind_list:
                cpu_cost_t.append(self.cloud_system.ms_kind_to_resource_need[ms_kind]["cpu"])
                mem_cost_t.append(self.cloud_system.ms_kind_to_resource_need[ms_kind]["mem"])
                disk_cost_t.append(self.cloud_system.ms_kind_to_resource_need[ms_kind]["disk"])
            cpu_cost_t = np.array(cpu_cost_t)
            mem_cost_t = np.array(mem_cost_t)
            disk_cost_t = np.array(disk_cost_t)
            ms_ratio_t = np.sum(weight_matrix_t, axis=1) / np.sum(weight_matrix_t)
            node_num_t = self.cloud_system.args.bare_metal_node_num
            print("start GA...")
            best_pop=GA_algorithm(weight_matrix_t, cpu_cost_t, mem_cost_t, disk_cost_t, ms_ratio_t, node_num_t)
            
            #获取ms_kind_list， node_index_list
            spec_ms_kind_list=[]
            spec_node_index_list=[]
            for node_index in range(best_pop.shape[0]):
                for ms_kind_index in range(best_pop.shape[1]):
                    ms_number=best_pop[node_index][ms_kind_index]
                    for _ in range(ms_number):
                        spec_ms_kind_list.append(system_ms_kind_list[ms_kind_index])
                        spec_node_index_list.append(node_index)
                        
            with open(init_deploy_strategy_file_path, "wb") as file:
                storage_data={
                    "ms_kind_list":spec_ms_kind_list,
                    "node_index_list":spec_node_index_list,
                    "resource_cost":self.cloud_system.ms_kind_to_resource_need
                }
                pickle.dump(storage_data, file)
            print("end init strategy!")
            self.execute_init_deploy(spec_ms_kind_list, spec_node_index_list)
            
            return
        
    def get_weight_matrix(self, system_ms_kind_list):
        #基于类型，统计邻接矩阵
        ms_kind_adj=np.zeros((len(system_ms_kind_list), len(system_ms_kind_list)))
        for service_name in self.cloud_system.service_to_callgraph_dict.keys():
            request_t=self.cloud_system.service_to_callgraph_dict[service_name]
            for task_t in request_t.start_task_list:
                self.get_weight_matrix_update(task_t, ms_kind_adj, system_ms_kind_list)
        return ms_kind_adj
        
    def get_weight_matrix_update(self,task, ms_kind_adj, system_ms_kind_list):
        for sub_task in task.sub_task_list:
            task_index=system_ms_kind_list.index(task.ms_kind)
            sub_task_index=system_ms_kind_list.index(sub_task.ms_kind)
            call_num=task.call_num
            ms_kind_adj[task_index][sub_task_index]+=call_num
            ms_kind_adj[sub_task_index][task_index]+=call_num
            self.get_weight_matrix_update(sub_task, ms_kind_adj, system_ms_kind_list)
        


    def get_adj_kind_matrix(self, each_ms_kind_deploy_number):
        #基于类型，统计邻接矩阵
        ms_kind_list=self.cloud_system.ms_kind_list
        ms_kind_adj=np.zeros((len(ms_kind_list), len(ms_kind_list)))
        for service_name in self.cloud_system.service_to_callgraph_dict.keys():
            request_t=self.cloud_system.service_to_callgraph_dict[service_name]
            for task_t in request_t.start_task_list:
                self.get_adj_matrix_update_ms_kind_adj(task_t, ms_kind_adj,ms_kind_list)
        #基于类型统计的邻接矩阵，计算计划生成的微服务call 邻接矩阵
        ms_list=[]
        for ms_kind in ms_kind_list:
            for order in range(each_ms_kind_deploy_number):
                ms_list.append(ms_kind)
                
        ms_adj=np.zeros((len(ms_list), len(ms_list)))
        for i in range(len(ms_list)):
            for j in range(0, i):
                pre_index_i=math.floor(i/each_ms_kind_deploy_number)
                pre_index_j=math.floor(j/each_ms_kind_deploy_number)
                call_num=ms_kind_adj[pre_index_i][pre_index_j]
                ms_adj[i][j]=call_num
                ms_adj[j][i]=call_num
        return ms_adj, ms_list
    
    
    
    def execute_init_deploy(self, ms_kind_list, node_index_list):
        #这里输入的ms_kind_list和cloud system 中的不一样，这里的可以重复，而cloud system中的不可以重复
        self.ms_id_list_exist=[]
        self.ms_kind_list_exist=[]
        self.ms_node_index_exist=[]
        self.ms_kind_to_number={}
        
        #根据社团划分结果进行部署
        for index in range(len(ms_kind_list)):
            ms_kind=ms_kind_list[index]
            node_index=node_index_list[index]
            result, ms_obj= self.cloud_system.bare_metal_node_list[node_index].deploy_ms(ms_kind, without_cold_start=True)
            assert result==True
                    
            self.ms_id_list_exist.append(ms_obj.ms_id)
            self.ms_kind_list_exist.append(ms_kind)
            self.ms_node_index_exist.append(node_index)
            if ms_kind not in self.ms_kind_to_number.keys():
                self.ms_kind_to_number[ms_kind]=1
            else:
                self.ms_kind_to_number[ms_kind]+=1
            
            self.set_ms_obj_end_time(ms_obj, 0)
        
        self.ms_call_matrix=np.zeros((len(self.ms_id_list_exist), len(self.ms_id_list_exist)))
    
    def set_ms_obj_end_time(self, ms_obj, end_time):
        self.ms_obj_to_end_time[ms_obj]=end_time
        return
    
    def update_ms_obj_end_time(self, ms_obj):
        estimate_end_time=ms_obj.get_estimate_end_time()
        self.ms_obj_to_end_time[ms_obj]=estimate_end_time
        return estimate_end_time
    
    def get_ms_obj_end_time(self, ms_obj):
        return self.ms_obj_to_end_time[ms_obj]
    
    def rm_ms_obj_end_time(self, ms_obj):
        del self.ms_obj_to_end_time[ms_obj]
    #######################################################################################
    #入口函数
    def do_schedule_deploy(self):
        #我们的调度方法
        not_scheduled_tasks=[]
        for task in self.cloud_system.pending_task_queue:
            if task.request.request_base==None:
                #获取模板request对象
                base_request=self.cloud_system.service_to_callgraph_dict[task.request.service_name]
                #拷贝一份request模板给task的request
                task.request.set_deepcopy_request_base(copy.deepcopy(base_request))
                #更新start_task_list
                task.request.request_base.update_base_start_task_list(task)
                #赋值可靠性和deadline
                task.request.request_base.reset_for_our_method(task.request.reliability)
                # for task_t in task.request.request_base.task_id_to_obj.values():
                #     task.request.request_base.
            
            spec_request_base=task.request.request_base
            task_base=spec_request_base.task_id_to_obj[task.task_id]
            task.ave_deal_time=task_base.ave_deal_time
            
            replica_num=self.schedule_get_replica_2(spec_request_base, task_base)
            task.set_replica_num(replica_num)
            result=self.schedule_to_ms(task, replica_num, task_base)
            #说明调度失败
            if result==False:
                not_scheduled_tasks.append(task)
                if self.print_level>10:
                    print(f"Time:{round(self.env.now)}\t (SCHE FAILED EVENT) \t{task.request.request_id}\t{task.task_id}")
            else:
                task.request.request_base.scheduled_task_list.append(task)
                # self.schedule_update_matrix(task)
        #清空队列
        self.cloud_system.pending_task_queue=not_scheduled_tasks
        return 
    
    
            
    #将task调度到微服务上
    def schedule_to_ms(self, task, replica_num, task_base):
        time_now=self.cloud_system.env.now
        if task.parent_task==None:
            parent_ms=None
        else:
            parent_ms=task.parent_task.first_parent_ms_obj
        #获取所有正在运行的微服务列表
        ms_obj_list=self.cloud_system.get_available_ms_obj_with_ms_kind(task.ms_kind)
        
        
        #获取每个微服务队列信息，并升序排序
        ##统计每个类型的微服务队列长度信息
        ms_obj_with_early_start_time_list=[]
        for ms_obj in ms_obj_list:
            #如果在禁止的列表中，则跳过
            # if ms_obj.ms_id in task.prohibit_ms_id_list or ms_obj.ms_id in prohibit_ms_id_by_parent_ms:
            #     continue
            #计算最早开始时间
            ms_idle_time=self.update_ms_obj_end_time(ms_obj)   #都是绝对时间
            TT=self.schedule_get_average_TT(task, ms_obj)
            early_start_time=max(time_now+TT, ms_idle_time)
            ms_obj_with_early_start_time_list.append([early_start_time, ms_obj])
         
        #需要评估一个新建的微服务的标志
        estimate_flage=True
        ##调度到微服务上
        for repeat_order in range(replica_num):
            if estimate_flage==True and self.cloud_system.args.ours_adjust_ms_flage==True:
                new_ms_start_time=self.estimate_new_ms_start_time(task, task.ms_kind, parent_ms)
                if new_ms_start_time>0:
                    ms_obj_with_early_start_time_list.append([new_ms_start_time, None])
                    estimate_flage=False
            ms_obj_with_early_start_time_list.sort(key=lambda x:x[0])
            [early_start_time, ms_obj]=ms_obj_with_early_start_time_list[0]
            if ms_obj!=None:
                # plan_end_time=early_start_time+task_base.ave_deal_time
                # self.set_ms_obj_end_time(ms_obj, plan_end_time)
                self.cloud_system.env.process(ms_obj.put_task_to_queue_event(task))
                #更新下一个task的开始时间(不需要加TT，因为已经在前面算过了)
                ms_obj_with_early_start_time_list[0][0]+=task_base.ave_deal_time
                task.aim_ms_obj_list.append(ms_obj)
                
            else:
                [cold_start_time, ms_obj]=self.remove_idle_deploy_spec_ms(task.ms_kind)
                assert ms_obj !=None
                # plan_end_time=early_start_time+task_base.ave_deal_time
                # self.set_ms_obj_end_time(ms_obj, plan_end_time)
                self.cloud_system.env.process(ms_obj.put_task_to_queue_event(task))
                TT=self.schedule_get_average_TT(task, ms_obj)
                end_time=max(cold_start_time, TT)+task_base.ave_deal_time
                ms_obj_with_early_start_time_list[0]=[end_time, ms_obj]
                task.aim_ms_obj_list.append(ms_obj)
                estimate_flage==True
        return        
            
    
    def estimate_new_ms_start_time(self, task, ms_kind, parent_ms):
        self.aim_node_obj, self.aim_ms_obj_list=self.evaluate_remove_idle_ms(ms_kind, parent_ms)
        if self.aim_node_obj==None:
            return -1
        
        new_ms_start_time=self.cloud_system.get_cold_start_time(ms_kind)
        if task.first_parent_ms_obj==None or task.first_parent_ms_obj.node_obj==self.aim_node_obj:
            return new_ms_start_time
        else:
            return new_ms_start_time+self.cloud_system.get_TT_time_cross_node(task)
    
    def evaluate_remove_idle_ms(self,  ms_kind, parent_ms):
        if parent_ms!=None:
            #如果parentms所在的node有足够空闲的资源，则直接部署
            if self.judge_resource_enough(parent_ms.node_obj, ms_kind):
                return parent_ms.node_obj, None
            #如果有空闲的，能放下目标ms，则直接部署
            for node in self.cloud_system.bare_metal_node_list:
                if self.judge_resource_enough(node, ms_kind):
                    return node, None
            
        #后面就是没有空余的资源，只能删除部分微服务以部署新的微服务
        node_score_list=[]
        for node in self.cloud_system.bare_metal_node_list:
            #score越小越好
            rm_ms_list, score=self.get_next_remove_idle_ms_for_new(node, ms_kind)
            if len(rm_ms_list)>0:
                node_score_list.append([score, node, rm_ms_list])
        if len(node_score_list)==0:
            return None, None
        node_score_list.sort(key=lambda x:x[0])
        [score, node, rm_ms_list]=node_score_list[0]
        return node, rm_ms_list
        
    def judge_resource_enough(self, node, ms_kind):
        cpu_need=self.cloud_system.ms_kind_to_resource_need[ms_kind]["cpu"]
        mem_need=self.cloud_system.ms_kind_to_resource_need[ms_kind]["mem"]
        disk_need=self.cloud_system.ms_kind_to_resource_need[ms_kind]["disk"]
        if node.cpu_rest>=cpu_need and node.mem_rest>=mem_need and node.disk_rest>=disk_need:
            return True
        else:
            return False
        
    def get_next_remove_idle_ms_for_new(self, node, ms_kind_aim):
        idle_percent_list=[]
        can_removed_ms_obj_list=[]
        for ms_obj in node.msid_to_msobj.values():
            ms_kind=ms_obj.ms_kind
            if self.ms_kind_to_number[ms_kind]==1:
                continue
            
            persist_time=self.cloud_system.env.now-ms_obj.start_time
            if ms_obj.can_be_rm():
                idle_percent=ms_obj.get_idle_percent()
                idle_percent_list.append([idle_percent, ms_obj, persist_time])
        if len(idle_percent_list)==0:
            return [], None
        
        idle_percent_list.sort(key=lambda x:x[0], reverse=True)

        cpu_need=self.cloud_system.ms_kind_to_resource_need[ms_kind_aim]["cpu"]-node.cpu_rest
        mem_need=self.cloud_system.ms_kind_to_resource_need[ms_kind_aim]["mem"]-node.mem_rest
        disk_need=self.cloud_system.ms_kind_to_resource_need[ms_kind_aim]["disk"]-node.disk_rest
        
        for [idle_percent, ms_obj, persist_time] in idle_percent_list:
            can_removed_ms_obj_list.append(ms_obj)
            cpu_need-=ms_obj.cpu_need
            mem_need-=ms_obj.mem_need
            disk_need-=ms_obj.disk_need
            if cpu_need<=0 and mem_need<=0 and disk_need<=0:
                return can_removed_ms_obj_list, len(can_removed_ms_obj_list)-(cpu_need+mem_need+disk_need)/300  #归一化
        return [], None
        
    
    def remove_idle_deploy_spec_ms(self, ms_kind_new):
        # aim_node_obj, ms_obj_rm= self.evaluate_remove_idle_ms(ms_kind_new)
        if self.aim_ms_obj_list!=None:
            #移除旧的
            for ms_obj in self.aim_ms_obj_list:
                self.aim_node_obj.remove_ms(ms_obj.ms_id)
                self.rm_ms_update_record(ms_obj.ms_id, ms_obj.ms_kind)
        #重新部署
        _, ms_obj=self.aim_node_obj.deploy_ms(ms_kind_new)
        if ms_obj==None:
            a=1
        node_index=self.cloud_system.bare_metal_node_list.index(self.aim_node_obj)
        self.add_ms_update_record(ms_obj.ms_id,ms_kind_new,node_index)
        early_start_time=self.cloud_system.env.now+self.cloud_system.get_cold_start_time(ms_kind_new)
        return [early_start_time, ms_obj]
    
    #计算平均传输时间TT
    def schedule_get_average_TT(self, task, ms_obj):
        TT=0
        if task.parent_task!=None:
            #处理父task有多个副本的情况，传输时间取平均值
            for parent_ms_obj in task.parent_task.aim_ms_obj_list:
                TT+=self.cloud_system.get_TT_time( task, ms_obj, parent_ms_obj)
            TT=TT/len(task.parent_task.aim_ms_obj_list)
        return TT
    
    def schedule_update_matrix(self, task):
        #如果是请求的第一个task，则无需更改matrix
        #对于一个副本需要被删除的，则不用记录
        if task.parent_task==None:
            return 
        for ms_obj in task.aim_ms_obj_list:
            if ms_obj.ms_id not in self.ms_id_list_exist:
                continue
            ms_id_index=self.ms_id_list_exist.index(ms_obj.ms_id)
            for ms_obj_parent_task in task.parent_task.aim_ms_obj_list:
                if ms_obj_parent_task.ms_id not in self.ms_id_list_exist:
                    continue
                ms_id_parent_index=self.ms_id_list_exist.index(ms_obj_parent_task.ms_id)
                self.ms_call_matrix[ms_id_index][ms_id_parent_index]+=1
                self.ms_call_matrix[ms_id_parent_index][ms_id_index]+=1
        
        
        
    def schedule_get_replica_1(self, request_base, task_base):
        #获取当前task需要的可靠性大小
        this_req=math.pow(request_base.reliability/request_base.already_reliability, 1/(request_base.all_task_num-request_base.already_num))
        
        #获取指定微服务故障参数
        ms_lambda=self.cloud_system.ms_kind_to_transient_lambda[task_base.ms_kind]
        #获取单个task无故障概率
        single_reliability=get_reliability_without_failure(task_base.ave_deal_time, ms_lambda)
        #获取副本数量
        replica_num=get_aim_replica_num(this_req, single_reliability)
        #更新和存储副本信息，可靠性信息
        request_base.already_reliability=request_base.already_reliability*(1-math.pow(1-single_reliability, replica_num))
        request_base.already_num+=1
        task_base.replica_num=replica_num
        return replica_num
        
    def schedule_get_replica_2(self, request_base, task_base):
        #获取剩余可靠性
        rest_reliability=request_base.reliability/request_base.already_reliability
        already_reliability_t=1
        
        rest_task_list=[]
        for task_t in request_base.task_id_to_obj.values():
            spec_value=task_t.ave_deal_time
            rest_task_list.append([spec_value, task_t])
        rest_task_list.sort(key=lambda x:x[0])
        all_task_num_t=len(rest_task_list)
        already_num_t=0
        for [spec_value, task_t] in rest_task_list:
            
            #获取当前task需要的可靠性大小
            this_req=math.pow(rest_reliability/already_reliability_t, 1/(all_task_num_t-already_num_t))
            
            #获取指定微服务故障参数
            ms_lambda=self.cloud_system.ms_kind_to_transient_lambda[task_t.ms_kind]
            #获取单个task无故障概率
            single_reliability=get_reliability_without_failure(task_t.ave_deal_time, ms_lambda)
            #获取副本数量
            replica_num=get_aim_replica_num(this_req, single_reliability)
            if task_t==task_base:
                task_base.replica_num=replica_num
                return replica_num
            else:
                already_reliability_t=already_reliability_t*(1-math.pow(1-single_reliability, replica_num))
                already_num_t+=1
        # #更新和存储副本信息，可靠性信息
        # request_base.already_reliability=request_base.already_reliability*(1-math.pow(1-single_reliability, replica_num))
        # request_base.already_num+=1
        # task_base.replica_num=replica_num
        # return replica_num
    
    
    def get_idle_ms_num(self, ms_kind):
        ms_obj_list=self.cloud_system.get_available_ms_obj_with_ms_kind(ms_kind)
        idle_ms_num=0
        for ms_obj in ms_obj_list:
            if ms_obj.get_queue_len()==0:
                idle_ms_num+=1
        return idle_ms_num
    
    def schedule_deploy_one_ms(self, ms_kind, aim_node):
        if aim_node!=None:
            flage, ms_id, node_id=aim_node.deploy_ms(ms_kind)
        else:
            flage=False
            
        if flage==True:
            #初始化的时候设置为冷启动结束时间
            self.set_ms_obj_end_time(aim_node.msid_to_msobj[ms_id], self.cloud_system.get_cold_start_time(ms_kind))
            return aim_node.msid_to_msobj[ms_id]
        else:
            node_num=self.cloud_system.args.bare_metal_node_num
            node_index_list=random.sample(range(node_num), node_num)
            for node_index in node_index_list:
                node=self.cloud_system.bare_metal_node_list[node_index]
                flage, ms_id, _ =node.deploy_ms(ms_kind)
                if flage==True:
                    #初始化的时候设置为冷启动结束时间
                    self.set_ms_obj_end_time(node.msid_to_msobj[ms_id], self.cloud_system.get_cold_start_time(ms_kind))
                    return node.msid_to_msobj[ms_id]
        
        print(f"schedule_random_deploy error (capacity lack)!")
        exit(-1)
        
    def deploy_adjust_ms_obj_num(self, ms_kind, change_num):
        if change_num==0:
            return
        elif change_num>0: #需要增加微服务
            #记录每个节点（社团）对当前类型微服务的需求程度
            cluster_acc_cross_dict={}
            for cluster_index in range(self.cloud_system.args.bare_metal_node_num):
                cluster_acc_cross_dict[cluster_index]=0
            #如果是增加，则以减少跨节点调用为目标
            #获取每个节点存在的指定类型的跨节点调用数量
            for row_index in range(len(self.ms_id_list_exist)):
                ms_kind_spec=self.ms_kind_list_exist[row_index]
                if ms_kind_spec != ms_kind:
                    continue
                cluster_index=self.ms_node_index_exist[row_index]
                for col_index in range(len(self.ms_id_list_exist)):
                    cluster_index_2=self.ms_node_index_exist[col_index]
                    if cluster_index_2 != cluster_index:
                        #不相等表明是跨社团的call
                        cluster_acc_cross_dict[cluster_index_2]+=self.ms_call_matrix[row_index][col_index]
            # 按 value 降序排序 key
            sorted_keys = sorted(cluster_acc_cross_dict, key=lambda k: cluster_acc_cross_dict[k], reverse=True)
            add_ms_num=0
            for node_index in cycle(sorted_keys):
                flage, ms_id, node_id=self.cloud_system.bare_metal_node_list[node_index].deploy_ms(ms_kind)
                if flage==True:
                    add_ms_num+=1
                    self.add_ms_update_record( ms_id, ms_kind, node_index)
                    ms_obj=self.cloud_system.bare_metal_node_list[node_index].msid_to_msobj[ms_id]
                    self.set_ms_obj_end_time(ms_obj, self.cloud_system.env.now+self.cloud_system.get_cold_start_time(ms_kind))
                if add_ms_num==change_num:
                    break
        
        #如果是减少，则删除被调用次数最少的ms
        elif change_num<0:
            reduce_num=-change_num
            #记录每个微服务被调用的次数（不区分是否同一节点）
            cluster_acc_call_dict={}
            row_sum=np.sum(self.ms_call_matrix, axis=1)
            for row_index in range(len(self.ms_id_list_exist)):
                ms_id=self.ms_id_list_exist[row_index]
                ms_kind_spec=self.ms_kind_list_exist[row_index]
                if ms_kind_spec != ms_kind:
                    continue
                cluster_acc_call_dict[ms_id]=row_sum[row_index]
            # 按 value 升序排序 key
            sorted_keys = sorted(cluster_acc_call_dict, key=lambda k: cluster_acc_call_dict[k])
            rm_ms_num=0
            for ms_id_t in cycle(sorted_keys):
                index=self.ms_id_list_exist.index(ms_id_t)
                cluster_index=self.ms_node_index_exist[index]
                ms_obj=self.cloud_system.bare_metal_node_list[cluster_index].msid_to_msobj[ms_id_t]
                self.rm_ms_obj_end_time(ms_obj)
                self.cloud_system.bare_metal_node_list[cluster_index].remove_ms(ms_id_t)
                self.rm_ms_update_record(ms_id_t,ms_kind)
                
                rm_ms_num+=1
                if rm_ms_num==reduce_num:
                    break
        else:
            print("change num wrong")
            exit(-1)
        return
    
    
    def deploy_migration_ms(self, ms_number):
        #随机选择ms_number个微服务，针对每个微服务判断来自哪个社团的call最多，则迁移到目标社团，如果来自当前社团的call最多则放弃迁移
        selected_ms_id_list=random.sample(self.ms_id_list_exist, ms_number)
        for ms_id in selected_ms_id_list:
            row_index=self.ms_id_list_exist.index(ms_id)
            ms_kind=self.ms_kind_list_exist[row_index]
            node_index_now=self.ms_node_index_exist[row_index]
            cluster_acc_call_dict={}
            for col_index in range(len(self.ms_id_list_exist)):
                if col_index != row_index:
                    node_index_t=self.ms_node_index_exist[col_index]
                    if node_index_t not in cluster_acc_call_dict.keys():
                        cluster_acc_call_dict[node_index_t]=self.ms_call_matrix[row_index][col_index]
                    else:
                        cluster_acc_call_dict[node_index_t]+=self.ms_call_matrix[row_index][col_index]
            # 按 value 降序排序 key
            sorted_keys = sorted(cluster_acc_call_dict, key=lambda k: cluster_acc_call_dict[k], reverse=True)
            for node_index_aim in sorted_keys:
                if node_index_aim == node_index_now:
                    break
                flage_t, ms_id_new, node_id=self.cloud_system.bare_metal_node_list[node_index_aim].deploy_ms(ms_kind)
                if flage_t==True:
                    self.add_ms_update_record( ms_id_new, ms_kind, node_index_aim)
                    self.cloud_system.bare_metal_node_list[node_index_now].remove_ms(ms_id)
                    self.rm_ms_update_record(ms_id, ms_kind)
                    break
                
        return 
    
    
    
    



        
    def add_ms_update_record(self, ms_id, ms_kind, ms_cluster_index):
        #列表中添加id
        self.ms_id_list_exist.append(ms_id)
        #添加ms kind信息
        self.ms_kind_list_exist.append(ms_kind)
        #添加社团索引信息
        self.ms_node_index_exist.append(ms_cluster_index)
        #更新ms kind 对应的num
        self.ms_kind_to_number[ms_kind]+=1
        #扩展矩阵
        new_row=np.zeros((1,self.ms_call_matrix.shape[1]))
        self.ms_call_matrix=np.vstack((self.ms_call_matrix, new_row))
        new_col=np.zeros((self.ms_call_matrix.shape[0],1))
        self.ms_call_matrix=np.hstack((self.ms_call_matrix, new_col))
        
    def rm_ms_update_record(self, ms_id, ms_kind):
        #列表中删除id
        ms_id_index=self.ms_id_list_exist.index(ms_id)
        self.ms_id_list_exist.pop(ms_id_index)
        #删除ms kind信息
        self.ms_kind_list_exist.pop(ms_id_index)
        #删除社团索引信息
        self.ms_node_index_exist.pop(ms_id_index)
        #更新ms kind 对应的num
        self.ms_kind_to_number[ms_kind]-=1
        assert self.ms_kind_to_number[ms_kind]>0
        #缩减矩阵
        self.ms_call_matrix=np.delete(self.ms_call_matrix,ms_id_index,0)
        self.ms_call_matrix=np.delete(self.ms_call_matrix,ms_id_index,1)
        
        
#***************************************************************************************************************************************  
    
    
    # def init_deploy_with_buffer(self):
    #     init_deploy_strategy_file_path=self.cloud_system.args.dealed_history_var_file+".init_deploy_strategy"
    #     if os.path.exists(init_deploy_strategy_file_path):
    #         with open(init_deploy_strategy_file_path, "rb") as file:
    #             storage_data=pickle.load(file)
    #             file_node_num=storage_data["node_num"]
    #             file_each_ms_kind_deploy_number=storage_data["buffer_ms_num"]
    #             if file_node_num != self.cloud_system.args.bare_metal_node_num or file_each_ms_kind_deploy_number!=self.buffer_ms_num:
    #                 self.init_deploy_get_strategy(init_deploy_strategy_file_path)
    #             else:
    #                 ms_kind_list=storage_data["ms_kind_list"]
    #                 node_index_list=storage_data["node_index_list"]
    #                 self.init_deploy_according_to_community_division(ms_kind_list, node_index_list)
    #     else:
    #         self.init_deploy_get_strategy(init_deploy_strategy_file_path)
    #     return
        
    # def init_deploy_get_strategy(self,init_deploy_strategy_file_path):
    #     if self.cloud_system.print_level>1:
    #         print("get init deploy strategy...")
    #     #获取社团的划分，基于微服务类型
    #     adj_kind_matrix, ms_kind_list=self.get_adj_kind_matrix(self.buffer_ms_num)
    #     node_index_list, cut=self.init_deploy_k_way_cut(adj_kind_matrix, self.cloud_system.args.bare_metal_node_num)
    #     self.init_deploy_according_to_community_division(ms_kind_list, node_index_list)
        
    #     with open(init_deploy_strategy_file_path, "wb") as file:
    #         storage_data={
    #             "node_num":self.cloud_system.args.bare_metal_node_num,
    #             "buffer_ms_num":self.buffer_ms_num,
    #             "ms_kind_list":ms_kind_list,
    #             "node_index_list":node_index_list,
    #         }
    #         pickle.dump(storage_data, file)
    #     return
    # def deploy(self, interval, each_ms_kind_deploy_number=0):
    #     print(f" {self.cloud_system.env.now} start deploy ...")
    #     if self.cloud_system.env.now==0:
    #         #初始化部署
    #         self.init_deploy(interval=interval, each_ms_kind_deploy_number=each_ms_kind_deploy_number)
    #     else:  
    #         #增量部署
    #         #先进行参数更新，参数更新需要前一个interval有数据
    #         #在第一次进行增量部署的时候不进行更新，因为部署结果不是来自于当前网络的输出结果
    #         if self.network_deploy_result==True:
    #             #更新过程
    #             for index in range(len(self.cloud_system.ms_kind_list)):
    #                 ms_kind=self.cloud_system.ms_kind_list[index]
    #                 reward=self.deploy_get_reward(ms_kind)
    #                 state=self.state_action_record[ms_kind]["state"]
    #                 action=self.state_action_record[ms_kind]["action"]
    #                 self.agent.update(state, action, reward)
                    
                    
    #         #再进行前向传播，确定微服务数量
    #         self.state_action_record={}   #记录信息 state, action, (reward 下一个轮回再计算)
    #         self.network_deploy_result=True
    #         for index in range(len(self.cloud_system.ms_kind_list)): 
    #             ms_kind=self.cloud_system.ms_kind_list[index]
    #             state=self.deploy_get_state(ms_kind)
    #             action=self.agent.get_action(state)
    #             temp_dict={}
    #             temp_dict["state"]=state
    #             temp_dict["action"]=action
    #             self.state_action_record[ms_kind]=temp_dict
    #             self.ms_num_for_ms_kind_aim[index]=action
    #         #上面得到了每个类型的微服务需要多少个
            
    #         #先做微服务增加减少
    #         ##获取增加减少的数量
    #         for index in range(len(self.cloud_system.ms_kind_list)):
    #             ms_kind=self.cloud_system.ms_kind_list[index]
    #             ms_kind_change=max(self.ms_num_for_ms_kind_aim[index],1)-self.ms_num_for_ms_kind_exist[index]
    #             self.deploy_adjust_ms_obj_num(ms_kind, ms_kind_change)

    #         #再做微服务迁移 指定单次迁移数量
    #         self.deploy_migration_ms(self.cloud_system.args.our_method_ms_migration_num)
    #     # 将matrix 中的元素除以2，以减弱历史数据的影响
    #     self.ms_call_matrix=self.ms_call_matrix/2
    #     print("end deploy ...")
        
    #     yield self.cloud_system.env.timeout(interval)
    #     if not self.cloud_system.system_end:
    #         self.cloud_system.env.process(self.deploy(interval))
    #     else:
    #         self.agent.save_model(self.agent_para_path)
    #     return
    
#以前的微服务初始化部署
# def init_deploy_with_distribute(self):
#         init_deploy_strategy_file_path=self.cloud_system.args.history_trace_file+f".{self.cloud_system.args.bare_metal_node_num}_{self.cloud_system.args.ms_number_for_each_node}.init_deploy_distribute"
#         if os.path.exists(init_deploy_strategy_file_path):
#             with open(init_deploy_strategy_file_path, "rb") as file:
#                 storage_data=pickle.load(file)
#                 ms_kind_list=storage_data["ms_kind_list"]
#                 node_index_list=storage_data["node_index_list"]
#                 self.init_deploy_according_to_community_division(ms_kind_list, node_index_list)
#         else:
#             if self.cloud_system.print_level>1:
#                 print("get init deploy strategy...")
            
            
#             adj_kind_matrix, ms_kind_list=self.get_adj_kind_matrix_distribute()
#             node_index_list, cut=self.init_deploy_k_way_cut(adj_kind_matrix, self.cloud_system.args.bare_metal_node_num)
#             self.init_deploy_according_to_community_division(ms_kind_list, node_index_list)
#             with open(init_deploy_strategy_file_path, "wb") as file:
#                 storage_data={
#                     "ms_kind_list":ms_kind_list,
#                     "node_index_list":node_index_list,
#                 }
#                 pickle.dump(storage_data, file)
#             return

#     def get_adj_kind_matrix_distribute(self):
#         #基于类型，统计邻接矩阵
#         ms_kind_list=self.cloud_system.ms_kind_list
#         ms_kind_adj=np.zeros((len(ms_kind_list), len(ms_kind_list)))
#         for service_name in self.cloud_system.service_to_callgraph_dict.keys():
#             request_t=self.cloud_system.service_to_callgraph_dict[service_name]
#             for task_t in request_t.start_task_list:
#                 self.get_adj_matrix_update_ms_kind_adj(task_t, ms_kind_adj, ms_kind_list)
#         #获取每个类型的微服务有多少个
#         ms_call_num=ms_kind_adj.sum(axis=1)
#         all_ms_num=self.cloud_system.args.bare_metal_node_num*self.cloud_system.args.ms_number_for_each_node
#         ms_index_list=random.choices(population=range(len(ms_call_num)),weights=ms_call_num,k=all_ms_num-len(ms_kind_list))
#         #基于类型统计的邻接矩阵，计算计划生成的微服务call 邻接矩阵
#         ms_list=ms_kind_list.copy()
#         for index in ms_index_list:
#             ms_list.append(ms_kind_list[index])
                
#         ms_adj=np.zeros((len(ms_list), len(ms_list)))
#         for i in range(len(ms_list)):
#             for j in range(0, i):
#                 pre_index_i=ms_kind_list.index(ms_list[i])
#                 pre_index_j=ms_kind_list.index(ms_list[j])
#                 call_num=ms_kind_adj[pre_index_i][pre_index_j]
#                 ms_adj[i][j]=call_num
#                 ms_adj[j][i]=call_num
                
#         return ms_adj, ms_list
    
    

#     def get_adj_kind_matrix(self, each_ms_kind_deploy_number):
#         #基于类型，统计邻接矩阵
#         ms_kind_list=self.cloud_system.ms_kind_list
#         ms_kind_adj=np.zeros((len(ms_kind_list), len(ms_kind_list)))
#         for service_name in self.cloud_system.service_to_callgraph_dict.keys():
#             request_t=self.cloud_system.service_to_callgraph_dict[service_name]
#             for task_t in request_t.start_task_list:
#                 self.get_adj_matrix_update_ms_kind_adj(task_t, ms_kind_adj,ms_kind_list)
#         #基于类型统计的邻接矩阵，计算计划生成的微服务call 邻接矩阵
#         ms_list=[]
#         for ms_kind in ms_kind_list:
#             for order in range(each_ms_kind_deploy_number):
#                 ms_list.append(ms_kind)
                
#         ms_adj=np.zeros((len(ms_list), len(ms_list)))
#         for i in range(len(ms_list)):
#             for j in range(0, i):
#                 pre_index_i=math.floor(i/each_ms_kind_deploy_number)
#                 pre_index_j=math.floor(j/each_ms_kind_deploy_number)
#                 call_num=ms_kind_adj[pre_index_i][pre_index_j]
#                 ms_adj[i][j]=call_num
#                 ms_adj[j][i]=call_num
                
#         return ms_adj, ms_list
    
#     def get_adj_matrix_update_ms_kind_adj(self,task, ms_kind_adj, ms_kind_list):
#         for sub_task in task.sub_task_list:
#             task_index=ms_kind_list.index(task.ms_kind)
#             sub_task_index=ms_kind_list.index(sub_task.ms_kind)
#             call_num=task.call_num
#             ms_kind_adj[task_index][sub_task_index]+=call_num
#             ms_kind_adj[sub_task_index][task_index]+=call_num
#             self.get_adj_matrix_update_ms_kind_adj(sub_task, ms_kind_adj, ms_kind_list)
    

        
        
#     def init_deploy_according_to_community_division(self, ms_kind_list, node_index_list):
#         #这里输入的ms_kind_list和cloud system 中的不一样，这里的可以重复，而cloud system中的不可以重复
#         self.ms_id_list_exist=[]
#         self.ms_kind_list_exist=[]
#         self.ms_node_index_exist=[]
#         self.ms_kind_to_number={}
        
#         pending_deploy_ms_list=[]
#         #根据社团划分结果进行部署
#         for index in range(len(ms_kind_list)):
#             ms_kind=ms_kind_list[index]
#             node_index=node_index_list[index]
#             result, ms_id, node_id= self.cloud_system.bare_metal_node_list[node_index].deploy_ms(ms_kind, without_cold_start=True)
#             if result==False:
#                 pending_deploy_ms_list.append(ms_kind)
#                 continue
                    
#             self.ms_id_list_exist.append(ms_id)
#             self.ms_kind_list_exist.append(ms_kind)
#             self.ms_node_index_exist.append(node_index)
#             if ms_kind not in self.ms_kind_to_number.keys():
#                 self.ms_kind_to_number[ms_kind]=1
#             else:
#                 self.ms_kind_to_number[ms_kind]+=1
            
#             ms_obj=self.cloud_system.bare_metal_node_list[node_index].msid_to_msobj[ms_id]
#             self.set_ms_obj_end_time(ms_obj, 0)
#         #对于首次未部署好的微服务进行重新部署
#         for ms_kind in pending_deploy_ms_list:
#             node_index_list=[i for i in range(self.cloud_system.args.bare_metal_node_num)]
#             while True:
#                 node_index=random.choice(node_index_list)
#                 result, ms_id, node_id= self.cloud_system.bare_metal_node_list[node_index].deploy_ms(ms_kind, without_cold_start=True)
#                 if result==False:
#                     node_index_list.remove(node_index)
#                     assert len(node_index_list)>0
#                     continue
#                 self.ms_id_list_exist.append(ms_id)
#                 self.ms_kind_list_exist.append(ms_kind)
#                 self.ms_node_index_exist.append(node_index)
#                 # index_new=self.cloud_system.ms_kind_list.index(ms_kind)
#                 # self.ms_num_for_ms_kind_exist[index_new]+=1
#                 ms_obj=self.cloud_system.bare_metal_node_list[node_index].msid_to_msobj[ms_id]
#                 self.set_ms_obj_end_time(ms_obj, 0)
#                 break
#         assert len(self.ms_id_list_exist)==self.cloud_system.args.bare_metal_node_num*self.cloud_system.args.ms_number_for_each_node  
         
#         self.ms_call_matrix=np.zeros((len(self.ms_id_list_exist), len(self.ms_id_list_exist)))
        
#     def init_deploy_k_way_cut(self,adj_matrix, partition_num, imbalance=1.2):
#         # ideal = 总顶点数 ÷ k
#         # 上限 = ideal × (1 + ufactor ⁄ 1000)
#         adj=sp.csr_matrix(adj_matrix)
#         # ① CSR & 对称化
#         csr = adj.tocsr()
#         if (csr - csr.T).nnz:
#             csr = csr.maximum(csr.T)

#         xadj     = csr.indptr.astype(np.int32)
#         adjncy   = csr.indices.astype(np.int32)
#         eweights = csr.data.astype(np.int32)
#         # print(f"xadj:{xadj}\nadjncy:{adjncy}\neweights:{eweights}")
#         # ② 负载不均衡：ufactor = (imbalance-1) × 1000
#         ufactor  = int(round((imbalance - 1) * 1000))   # 1.05 → 50

#         # ③ 构造 Options —— 只能用类，不能用 dict
#         opts = Options(ufactor=ufactor, numbering=0)    # numbering=0 表示 C-style 0…n-1

#         # ④ 调用 part_graph（无 ubvec / adjwgt）
#         objval, parts = pymetis.part_graph(
#             partition_num,
#             xadj=xadj,
#             adjncy=adjncy,
#             eweights=eweights,
#             options=opts,
#         )
#         return np.asarray(parts), objval